#ifndef THREADTREE_H__
#define THREADTREE_H__

#define datatype char

typedef enum
{
	LINK,
	THREAD
} Tag;

typedef struct ThreadTreeNode
{
	datatype data;
	struct ThreadTreeNode *left;
	struct ThreadTreeNode *right;
	Tag ltag, rtag;
} ThreadTreeNode;

typedef struct ThreadTree
{
	ThreadTreeNode *node;
	datatype refvalue;
} ThreadTree;

void Init(ThreadTree *, datatype);

void Create(ThreadTree *tree, char **str); //先序遍历建立二叉树,还没有线索
void Create_(ThreadTree *tree, ThreadTreeNode **node, char **str);

void CreateInThread(ThreadTree *tree); //创建中序的线索二叉树
void CreateInThread_(ThreadTreeNode *node, ThreadTreeNode **pre);

void CreatePreThread(ThreadTree *tree); //创建前序的线索二叉树
void CreatePreThread_(ThreadTreeNode *node, ThreadTreeNode **pre);

ThreadTreeNode *First(ThreadTreeNode *node); //找一颗中序线索二叉树第一个结点

ThreadTreeNode *Last(ThreadTreeNode *node); //找一颗中序线索二叉树最后一个结点

ThreadTreeNode *Next(ThreadTreeNode *node, ThreadTreeNode *cur); //找一颗中序线索二叉树中某一个结点的后一个结点

ThreadTreeNode *Prio(ThreadTreeNode *node, ThreadTreeNode *cur); //找一颗中序线索二叉树中某一个结点的前一个结点

void InOrder(ThreadTreeNode *node); //中序线索二叉树下的中序遍历

ThreadTreeNode *Search(ThreadTreeNode *node, datatype key); //在一颗线索二叉树下查找某个结点

ThreadTreeNode *Parent(ThreadTreeNode *node, ThreadTreeNode *cur); //在一颗线索二叉树下查找某个结点的父结点

#endif